Vào thế kỷ 17, dưới thời các chúa Nguyễn, "Phủ Cam" (府 柑) vốn là một phủ, là chỗ ở của các hoàng tử.[2]

Thời gian đó, đa số các nhà thờ Công giáo ở Huế chỉ là những nhà nguyện đơn giản với sườn gỗ, mái tranh. Khi các vua chúa Việt Nam hạ lệnh cấm đạo gay gắt thì chúng bị triệt hạ đi. Dưới thời Pháp thuộc, các nhà thờ được xây dựng trở lại và dần được nâng cấp thêm khang trang, bề thế. Nhà thờ Phủ Cam là một trường hợp như vậy.

Năm 1682, linh mục Langlois cho xây dựng nhà nguyện Phủ Cam bằng tranh tre tại xóm Đá, sát bờ sông An Cựu.

Hai năm sau, linh mục đã cho triệt giải nhà nguyện này và mua đất trên đồi Phước Quả để xây dựng một nhà thờ to lớn hơn và kiên cố bằng đá, lúc đó nhà thờ quay về hướng Tây. Đó là một công trình to lớn, chắc chắn và được chúa Nguyễn Phúc Tần thán phục. Nhưng đến thời chúa Nguyễn Phúc Chu, vào năm 1698, ngôi nhà thờ ấy bị triệt giải hoàn toàn.[3]

Sau đó 2 thế kỷ, vào năm 1898, Giám mục Eugène Marie Allys (Giám mục Lý) đã cho xây mới Nhà thờ Phủ Cam bằng gạch, mái lợp ngói khá đồ sộ ở vị trí cũ nhưng mặt quay về hướng Bắc. Công trình này do chính Giám mục thiết kế và giám sát thi công đã hoàn thành vào năm 1902.

Năm 1960, sau khi Giáo phận Huế được nâng lên hàng Tổng giáo phận và Tổng Giám mục Phêrô Máctinô Ngô Đình Thục từ Vĩnh Long về nhận chức Tổng Giám mục Huế, ông đã cho phá hủy toàn bộ nhà thờ Phủ Cam cũ và khởi công xây cất Nhà thờ chính tòa mới với đồ án do kiến trúc sư Ngô Viết Thụ thực hiện.

Ðầu năm 1963, nhà thờ bắt đầu được khởi công xây dựng. Trong khi việc xây dựng đang tiến hành thì xảy ra cuộc đảo chánh ngày 1 tháng 11 năm 1963, tổng thống Ngô Đình Diệm bị sát hại và Tổng Giám mục Ngô Đình Thục lúc đó đang đi họp Công đồng Vatican II bên Roma, vì hoàn cảnh chính trị không trở về Việt Nam, việc xây dựng cũng bị chững lại.

Tuy việc xây dựng vẫn được tiến hành song tiến độ rất chậm chạp, tới năm 1967 nhà thờ mới lên được phần cung thánh.

Trong sự kiện Tết Mậu Thân (1968), bom đạn đã làm hư hại phần lớn công trình kiến thiết nhà thờ và việc xây dựng đã gặp nhiều trở ngại mãi cho đến trước 1975 vẫn chưa hoàn thành.

Sau 1975, do hoàn cảnh, mọi công tác xây dựng đều tiến hành chậm chạp, và đến năm 1995, phần thân nhà thờ về cơ bản được hoàn thành.

Năm 1999, để chuẩn bị cho hai ngày 28 và 29 tháng 6 năm 2000, là ngày Tổng Giáo phận Huế cung hiến nhà thờ chính tòa Phủ Cam nhân dịp kỷ niệm 150 năm ngày thành lập Giáo phận Huế (kể từ khi tách rời khỏi Giáo phận Đàng Trong), Tổng Giám mục Stêphanô Nguyễn Như Thể hạ quyết tâm bằng đủ mọi cách phải hoàn thành các trang trí bên trong nhà thờ và hai tháp chuông trước tiền đường. Công trình xây cất đã hoàn tất vào tháng 5 năm 2000.

Như thế, trải qua 3 đời Giám mục - từ Tổng Giám mục Ngô Đình Thục đến Tổng Giám mục Nguyễn Kim Điền và Tổng Giám mục Nguyễn Như Thể - sau gần 40 năm xây dựng, nhà thờ chính tòa Phủ Cam mới hoàn thành với diện mạo như hiện nay.